﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
public class Solution64
{
    public int MinPathSum(int[][] grid)
    {
        int m=grid.Length;
        int n = grid[0].Length;

        //最上面，只能从左边过来
        int[][] dp = new int[m][];
        for (int i = 0; i < m; i++)
        {
            dp[i]=new int[n];
        }

        dp[0][0] = grid[0][0];
        for (int i = 1; i < m; i++)
        {

          
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }

        for (int i = 1; i < n; i++)
        {

            dp[0][i] = dp[0][i - 1] + grid[0][i];
           
        }

        for (int i = 1; i < m; i++)
        {

            for(int j = 1; j < n; j++)
            {
                dp[i][j] = Math.Min(dp[i - 1][j], dp[i ][j - 1]) + grid[i][j];

            }
        }


        return dp[m-1][n - 1];


    }
}

class Program
{
    static void Main64(string[] args)
    {
        Solution64 solution = new Solution64();

        int[][] grid = [[1, 3, 1], [1, 5, 1], [4, 2, 1]];
        int res=   solution.MinPathSum(grid);
        Console.WriteLine(res);

    }
}
